package com.zwj.interview.单调栈;

import java.util.Stack;

/**
 * 请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积
 */
@Deprecated
public class 最大矩阵面积 {

    /**
     * 数组heights用来记录以某一行作为基线的直方图的每根柱子的高度。如果矩阵中某个格子的值为0，
     * 那么它所在的柱子的高度为0；如果矩阵中某个格子的值为1，那么它所在的柱子的高度是以上一行作为基线的直方图同一位置的柱子的高度加1
     * @param matrix
     * @return
     */
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        //遍历每一行
        for (char[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                if (row[i] == '0') {
                    heights[i] = 0;
                } else {
                    heights[i]++;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    public int largestRectangleArea(int[] heights) {
        // 初始化最终结果为0
        int res = 0;
        //栈中存元素下标，栈底到栈顶一次增加
        Stack<Integer> stack = new Stack<>();
        // 将给定的原数组左右各添加一个元素0
        int[] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int i = 1; i < heights.length + 1; i++) {
            newHeights[i] = heights[i - 1];
        }
        // 开始遍历
        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空且当前考察的元素值小于栈顶元素值，
            // 则表示以栈顶元素值为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                // 弹出栈顶元素
                int cur = stack.pop();
                // 获取栈顶元素对应的高
                int curHeight = newHeights[cur];
                // 栈顶元素弹出后，新的栈顶元素就是其左侧边界
                int leftIndex = stack.peek();
                // 右侧边界是当前考察的索引
                int rightIndex = i;
                // 计算矩形宽度
                int curWidth = rightIndex - leftIndex - 1;
                // 计算面积
                res = Math.max(res, curWidth * curHeight);
            }
            // 当前考察索引入栈
            stack.push(i);
        }

        return res;
    }
}
